// 题目描述：
// 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

// 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

// 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。



// 示例 1:

// 输入: nums = [1,2,3,4]
// 输出: [24,12,8,6]
// 示例 2:

// 输入: nums = [-1,1,0,-3,3]
// 输出: [0,0,9,0,0]

// 自己的答案（超越99.39%）：
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
    let newArr = []
    const calculateFun = (index) => {
      return nums.filter((e, i) => i !== index).reduce((accumulator, currentValue) => accumulator * currentValue, 1);
    }
    // nums.forEach((e, i) => { // 时间复杂度和空间复杂度过高
    //   newArr[i] = calculateFun(i)
    // })
    // return newArr
    
    const accResult = nums.reduce((accumulator, currentValue) => accumulator * currentValue, 1);
    nums.forEach((e, i) => {
        newArr[i] = e === 0 ? calculateFun(i) : accResult / e
    })
    return newArr
};

// 官方答案：
// 思路：从左往右遍历，记录从左到当前位置前一位的乘积，然后从右往左遍历，从左到当前位置前一位的乘积乘上右边元素的积。
// 复杂度：时间复杂度O(n)，空间复杂度O(1)
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
    let ans = [1]
    //前项积
    for (let i = 1; i < nums.length; i++) {
        ans[i] = ans[i - 1] * nums[i - 1]
    }
    // 当前项等于前项积乘以后项积
    let end = 1
    for (let j = nums.length - 1; j >= 0; j--) {
        ans[j] *= end
        end *= nums[j]
    }
    return ans
};